#include <iostream>
#include <vector>
using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> leftMax(n, 0);
    vector<int> rightMax(n, 0);

    int curMax = 0;
    for (int i = 0; i < n; i++) {
        if (height[i] > curMax) {
            curMax = height[i];
        }
        leftMax[i] = curMax;
    }
    curMax = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (height[i] > curMax) {
            curMax = height[i];
        }
        rightMax[i] = curMax;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}